class Solution {
public:
    void inorder(Node* root, Node*& prev)
    {
        if (root == nullptr)
            return;

        inorder(root->left, prev);
        root->left = prev;
        if (prev)
        {
            prev->right = root;
        }
        inorder(root->right, prev);
    }
    Node* treeToDoublyList(Node* root) {
        Node* prev = nullptr;
        inorder(root, prev);
        Node* head = root;
        while (head && head->left)
        {
            head = head->left;
        }
        return head;
    }
};